//8数码问题
//使用A*搜索算法解决8-puzzle及其自然概括的问题
//8 拼图 是一种滑动拼图 ，在 3×3 的网格上进行，网格上有 8 个标有 1 到 8 的方格，外加一个空白方格。
//目标是使用尽可能少的移动次数重新排列方格，使它们按行主序排列。您可以将方格水平或垂直滑动到空白方格中
//使用A*搜索算法解决
//优先级队列，就是堆
//这里先说明一下A*搜索算法
//A*搜索算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。
//拿2D游戏举例，在地图里不仅有怪物和玩家，还有很多障碍物，你需要一个智能的怪物按照最短路径去追逐玩家，
//那么在类似这种的场景下A*搜索算法会是最好的选择之一
//A*搜索算法的思想是这样的：假设一个网格图，我们需要从其中一点到另一点，然后两点之间有障碍
//这个时候我们用一个优先队列（堆）作为算法的核心，而这里优先队列中判断大小的方式就是一个综合优先级
//一个点的综合优先级(f(n))是从起点到现在这个点的代价(g(n))和这个点到达终点的预计代价的和（h(n)）---f(n)=g(n)+h(n)
//明白运用综合优先级作为判断大小的依据维护优先队列，A*搜索算法的步骤就简单了
//首先我们将初始搜索节点插入优先队列中
//这里开始循环，删除最小节点，并插入所有相邻搜索节点(网格图来说就是上下左右呗)
//重复循环，直到到达目标节点
//这里有两个需要做的优化：
//1.假如一个节点已经走到下一个节点了，那么这时候考虑下一个节点的相邻结点的时候，不要再把这个节点考虑进来
//2.缓存h(n)，就是在每次构造相邻节点的时候就把这个计算好，等后面需要的时候直接调用
//有些情况是不可解决的,根据是否可接分为两种情况
//1.可解
//2.通过修改初始情况（交换任意一对tile）可解
//所以要同步运行两个Board实例，一个是原本的，一个是交换了一对tile的，这两个中会有一个最终可解
import java.util.LinkedList;
import java.util.Scanner;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdOut;
public class Solver {
boolean solverble=false;
LinkedList<Board> solution;
// find a solution to the initial board (using the A* algorithm)
public Solver(Board initial)
{
    solution=new LinkedList<Board>();
    //创建twin以及两个对应的优先队列
    Board twin=initial.twin();    //找到twin Board，下面需要同时运行这两个
    twin.moves=0;initial.moves=0;
    MinPQ<Board> ini=new MinPQ<Board>(initial.manhattanOrder());
    MinPQ<Board> twMinPQ=new MinPQ<Board>(initial.manhattanOrder());

    //初始节点插入优先队列中
    ini.insert(initial);
    twMinPQ.insert(twin);

    int moves=0;//看看循环次数
    Board min_ini;
    Board min_twMinPQ;
    Board pre_min_ini=null;
    Board pre_min_twMinPQ=null;
    //开始循环
    while(true)
    {
        //删除最小节点
        min_ini=ini.delMin();
        min_twMinPQ=twMinPQ.delMin();
        //将min_ini放入solution序列中
        solution.addLast(min_ini);
        //这里先检测是否找到了goal Board
        if(min_ini.isGoal())
        {
            solverble=true;
            break;
        }
        if(min_twMinPQ.isGoal())
        {
            break;
        }
        //插入邻节点，先插原来的Board
        for(Board neighbor:min_ini.neighbors())
        {
            neighbor.moves=min_ini.moves+1;
            int neighbor_key=neighbor.manhattan()+moves();
            if(pre_min_ini!=null&&neighbor.equals(pre_min_ini))
            {
              continue;
            }
            neighbor.key+=neighbor.moves;
            ini.insert(neighbor);
        }
        //再插交换后的Board
        for(Board neighbor:min_twMinPQ.neighbors())
        {
            neighbor.moves=min_twMinPQ.moves+1;
            int neighbor_key=neighbor.manhattan()+moves();
            if(pre_min_twMinPQ!=null&&neighbor.equals(pre_min_twMinPQ))
            {
                continue;
            }
            neighbor.key+=neighbor.moves;
            twMinPQ.insert(neighbor);
        }

        pre_min_ini=min_ini;
        pre_min_twMinPQ=min_twMinPQ;
        moves++;
    }

}

// is the initial board solvable? (see below)
public boolean isSolvable()
{
  return solverble;
}

// min number of moves to solve initial board; -1 if unsolvable
public int moves()
{
    if(solverble)
    {
       return solution.getLast().moves;
    }
    else
    { 
       return -1;
    }
}

// sequence of boards in a shortest solution; null if unsolvable
public Iterable<Board> solution()
{
   if(solverble)
   {
    return solution;
   }
   else
   {
    return null;
   }
}

// test client (see below)
public static void main(String[] args)
{
    Scanner scanner=new Scanner(System.in);
         int n = scanner.nextInt(); 
         int[][] tiles = new int[n][n];
         Board initial = new Board(tiles);
        for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            initial.tiles[i][j] = scanner.nextInt();

    initial.moves=0;
    initial.key=initial.manhattan()+initial.moves;

    // solve the puzzle
    Solver solver = new Solver(initial);

    // print solution to standard output
    if (!solver.isSolvable())
        StdOut.println("No solution possible");
    else {
        StdOut.println("Minimum number of moves = " + solver.moves());
        for (Board board : solver.solution())
            StdOut.println(board);
    }
}
}
